import java.util.HashMap;
import java.util.Map;

public class Solution236 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int deep1=-1,deep2=-1;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode,TreeNode> map=new HashMap<>();
        dfs(map,root,null,p,q,0);
        while (deep1>deep2){
            p=map.get(p);
            deep1--;
        }
        while (deep2>deep1){
            q=map.get(q);
            deep2--;
        }
        while (p!=q){
            p=map.get(p);
            q=map.get(q);
        }
        return p;
    }

    private void dfs(Map<TreeNode, TreeNode> map, TreeNode root,TreeNode last,TreeNode p,TreeNode q,int deep) {
        if (root==null){
            return;
        }
        map.put(root,last);
        if (root==p){
            deep1=deep;
        }
        if (root==q){
            deep2=deep;
        }
        dfs(map,root.left,root,p,q,deep+1);
        dfs(map,root.right,root,p,q,deep+1);
    }

    public static void main(String[] args) {
        TreeNode t1=new TreeNode(5,new TreeNode(6),new TreeNode(2,new TreeNode(7),new TreeNode(4)));
        TreeNode t2=new TreeNode(1,new TreeNode(0),new TreeNode(8));
        System.out.println(new Solution236().lowestCommonAncestor(new TreeNode(3,t1,t2),t1,t2).val);
    }
}
